#ifndef STX_BINARY_SEARCH_TREE_HPP
#define STX_BINARY_SEARCH_TREE_HPP

#include <cstddef>
#include <functional>
#include <memory>

namespace stx {

template <typename T>
struct binary_search_tree_node;

template <typename T>
struct binary_search_tree_node
{
    typedef binary_search_tree_node<T> this_type;
    typedef T value_type;
    
    binary_search_tree_node(
        const value_type& value,
        this_type* parent = 0,
        this_type* left_child = 0,
        this_type* right_child = 0):
        value_(value),
        parent_(parent),
        left_child_(left_child),
        right_child_(right_child)
    {
    }
    
    value_type value_;
    this_type* parent_;
    this_type* left_child_;
    this_type* right_child_;
    
    value_type value() const
    {
        return value_;
    }
    
    this_type* parent() const
    {
        return parent_;
    }
    
    this_type* left_child() const
    {
        return left_child_;
    }
    
    this_type* right_child() const
    {
        return right_child_;
    }
    
    bool is_root() const
    {
        return !parent_;
    }
    
    bool is_leaf() const
    {
        return !(left_child_ || right_child_);
    }
};

template<
    typename T,
    typename Compare = std::less<T>,
    typename Allocator = std::allocator<binary_search_tree_node<T> > >
class binary_search_tree: public Allocator
{
public:
    
    template<typename U, typename C, typename A, typename Ostream>
    friend inline Ostream& pretty_print(const binary_search_tree<U, C, A>& b, Ostream& os);
    
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef binary_search_tree_node<T> node_t;
    typedef Compare compare_type;
    typedef Allocator allocator_type;
    typedef const_reference value_input_type;
    typedef reference value_output_type;
    
    binary_search_tree()
    {
        root(0);
    }
    
    binary_search_tree(value_input_type value)
    {
        create_node(root(), value);
    }
    
    ~binary_search_tree()
    {
        if (root()) {
            delete_node(root());
        }
    }
    
    void create_node(
        node_t*& node,
        value_input_type value,
        node_t* parent = 0,
        node_t* left_child = 0,
        node_t* right_child = 0)
    {
        node = get_allocator()->allocate(1);
        //get_allocator()->construct(node, node_t(value, parent, left_child, right_child));
        node->value_ = value;
        node->parent_ = parent;
        node->left_child_ = left_child;
        node->right_child_ = right_child;
    }
    
    void delete_node(node_t* node)
    {
        if (node->left_child()) {
            delete_node(node->left_child());
        }
        if (node->right_child()) {
            delete_node(node->right_child());
        }
        get_allocator()->destroy(node);
        get_allocator()->deallocate(node, 1);
    }
    
    allocator_type* get_allocator()
    {
        return static_cast<allocator_type*>(this);
    }
    
    node_t* root()
    {
        return root_;
    }
    
    const node_t* root() const
    {
        return root_;
    }
    
    void insert(value_input_type value)
    {
        node_t* node = root(), *parent = 0;
        if (!node) {
            create_node(node, value);
            size_ += 1;
            root(node);
            return;
        }
        bool is_inserted = false;
        bool is_left_child;
        compare_type cmp;
        while (!is_inserted) {
            parent = node;
            if (cmp(value, node->value())) {
                node = node->left_child();
                is_left_child = true;
            } else {
                node = node->right_child();
                is_left_child = false;
            }
            if (!node) {
                create_node(node, value, parent);
                size_ += 1;
                if (is_left_child) {
                    parent->left_child_ = node;
                } else {
                    parent->right_child_ = node;
                }
                is_inserted = true;
            }
        }
    }
    
    value_type min()
    {
        node_t* node = root();
        while (node->left_child()) {
            node = node->left_child();
        }
        return node->value();
    }
    
    value_type max()
    {
        node_t* node = root();
        while (node->right_child()) {
            node = node->right_child();
        }
        return node->value();
    }
    
    node_t* find(value_input_type value)
    {
        node_t* ret = 0, *node = root();
        if (!node) {
            return ret;
        }
        compare_type cmp;
        while (node) {
            if (value == node->value()) {
                ret = node;
                break;
            } else if (cmp(value, node->value())) {
                node = node->left_child();
            } else {
                node = node->right_child();
            }
        }
        return ret;
    }
    
    node_t* common_ancestor(node_t* node1, node_t* node2)
    {
        node_t* ret = 0;
        if (node1 == node2) {
            return node1;
        }
        node_t* node = root();
        compare_type cmp;
        while (1) {
            if (node == node1 || node == node2) {
                ret = node;
                break;
            }
            if (cmp(node1->value(), node->value()) && cmp(node2->value(), node->value())) {
                node = node->left_child();
                continue;
            } else if (cmp(node->value(), node1->value()) && cmp(node->value(), node2->value())) {
                node = node->right_child();
                continue;
            } else {
                ret = node;
                break;
            }
        }
        return ret;
    }
    
    size_type size() const
    {
        return size_;
    }
    
private:
    
    void root(node_t* node)
    {
        root_ = node;
    }
    
    void size(const size_type& n)
    {
        size_ = n;
    }
    
    node_t* root_;
    
    size_type size_;
    
};

} // namespace stx

#include <vector>
#include <iostream>

template<typename U, typename C, typename A, typename Ostream>
inline Ostream& pretty_print(Ostream& os, const stx::binary_search_tree<U, C, A>& b)
{
    using namespace std;
    //typedef const stx::binary_search_tree_node<U> node_t;
    typedef const typename stx::binary_search_tree<U, C, A>::node_t node_t;
    vector<vector<node_t*> > graph;
    size_t num_nodes = 1;
    node_t* node = b.root();
    graph.resize(1);
    graph[0].push_back(node);
    size_t i, j, current_layer = 1, num_not_leaf_nodes;
    while (1) {
        num_nodes *= 2;
        graph.push_back(vector<node_t*>(num_nodes, 0));
        num_not_leaf_nodes = 0;
        for (i = 0; i < graph[current_layer - 1].size(); ++i) {
            node = graph[current_layer - 1][i];
            if (node) {
                if (node->left_child()) {
                    graph[current_layer][2*i] = node->left_child();
                    num_not_leaf_nodes += 1;
                }
                if (node->right_child()) {
                    graph[current_layer][2*i + 1] = node->right_child();
                    num_not_leaf_nodes += 1;
                }
            }
        }
        current_layer += 1;
        if (num_not_leaf_nodes == 0) {
            break;
        }
    }
    size_t k, n = graph.back().size() / 2, m = graph.back().size();
    for (i = 0; i < graph.size(); ++i) {
        for (j = 0; j < n; ++j) {
            os << "\t";
        }
        n /= 2;
        for (j = 0; j < graph[i].size(); ++j) {
            if (graph[i][j] != 0) {
                os << graph[i][j]->value();
            } else {
                os << "NULL";
            }
            for (k = 0; k < m; ++k) {
                os << "\t";
            }
        }
        m /= 2;
        os << "\n";
    }
    return os;
}

#endif // STX_BINARY_SEARCH_TREE_HPP
